package pers.qianyu.month_202103.date_20210324;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 456. 132 模式
 * https://leetcode-cn.com/problems/132-pattern/
 *
 * @author mizzle rain
 * @date 2021-03-24 20:14
 */
public class Find132pattern {
    // 暴力解法
    public boolean find132pattern1(int[] nums) {
        int n = nums.length;
        if (n == 0) return false;
        int min = nums[0];
        for (int i = 1; i < n; i++) {
            for (int j = n - 1; j > i; j--) {
                if (nums[j] > min && nums[j] < nums[i] && nums[i] > min) {
                    return true;
                }
            }
            min = Math.min(min, nums[i]);
        }
        return false;
    }

    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        if (n < 3) return false;
        Deque<Integer> st = new ArrayDeque<>();
        int k = Integer.MIN_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] < k) {
                // 说明k的值已经被修改了，就说明k前面有比k大的数
                return true;
            }
            while (!st.isEmpty() && st.getLast() < nums[i]) {
                k = st.removeLast();
            }
            st.addLast(nums[i]);
        }
        return false;
    }

    @Test
    public void test1() {
        boolean r = new Find132pattern().find132pattern(new int[]{1, 2, 3, 4});
        Assert.assertFalse(r);
    }

    @Test
    public void test2() {
        boolean r = new Find132pattern().find132pattern(new int[]{1, 0, 1, -4, -3});
        Assert.assertFalse(r);
    }

    @Test
    public void test3() {
        boolean r = new Find132pattern().find132pattern(new int[]{3, 1, 4, 2});
        Assert.assertTrue(r);
    }
}
